Aufgabe: Schreiben Sie reguläre Ausdrücke für die folgenden Sprachen:

a) Die Menge der Zeichenreihen über dem Alphabet a, b, c, die mindestens ein a und ein b enthalten.

b) Die Menge der Zeichenreihen aus Nullen und Einsen, deren zehntes Symbol von rechts eine Eins ist.

c) Die Menge der Zeichenreihen aus Nullen und Einsen, die mindestens ein Paar aufeinander folgender Einser enthalten.

Lösung:

a) c^{∗}a(a + c)^{∗}b(a + b + c)^{∗} + c^{∗}b(b + c)^{∗}a(a + b + c)^{∗}

b) (0 + 1)^{∗}1(0 + 1)^{9}

c) (0 + 1)^{∗}11(0 + 1)^{∗}